package com.xw.class11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import static com.xw.class10.Code02_IteratorBinaryTree.preOrder;

/**
 * @author XW
 * @data 2023/7/11 13:52
 * @description 序列化和反序列化一棵树
 */
public class Code02_SerializeAndDeserializeTree {
    public static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value){
            this.value = value;
        }
    }

    /**
     * 前序序列化一棵树 注意为空的节点也需要加入进来
     * @param head
     * @return
     */
    public static Queue<String> preSerializeTree(Node head){
        Queue<String> queue = new LinkedList<>();
        preOrder(head,queue);
        return queue;
    }

    private static void preOrder(Node head, Queue<String> queue) {
        if(head == null){
            queue.add(null);
        }else{
            queue.add(String.valueOf(head.value));
            preOrder(head.left,queue);
            preOrder(head.right,queue);
        }
    }

    /**
     *先序反序列化构建树
     * @param queue
     * @return
     */
    public static Node deSerializeTreeByPre(Queue<String> queue){
        if(queue.isEmpty()){
            return null;
        }
        return preBuildTree(queue);
    }

    private static Node preBuildTree(Queue<String> queue) {
        String value = queue.poll();
        if(null == value){
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.left = preBuildTree(queue);
        head.right = preBuildTree(queue);
        return head;
    }

    /**
     * 构建 后序队列
     * @param head
     * @return
     */
    public static Queue<String> buildPostOrder(Node head){
        Queue<String> queue = new LinkedList<>();
        postOrder(head,queue);
        return queue;
    }

    private static void postOrder(Node head, Queue<String> queue) {
        if(head == null){
            queue.add(null);
        }else{
            postOrder(head.left,queue);
            postOrder(head.right,queue);
            queue.add(String.valueOf(head.value));
        }
    }

    /**
     * 后序反序列化构建树  后续遍历后队列的顺序为  左右头  弹出后加入栈 ，从栈里弹出的顺序为 头右左 ，类似先序构建树
     * @param queue
     * @return
     */
    public static Node deSerializeTreeByPost(Queue<String> queue){
        if(queue.isEmpty()){
            return null;
        }
        Stack<String> stack = new Stack<>();
        while (!queue.isEmpty()) {
            stack.push(queue.poll());
        }
        return postBuildTree(stack);
    }

    private static Node postBuildTree(Stack<String> stack) {
        String value = stack.pop();
        if(null == value){
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.right = postBuildTree(stack);
        head.left = postBuildTree(stack);
        return head;
    }

    public static Queue<String> levelSerializeTree(Node head){
        Queue<String> queue = new LinkedList<>();
        if(null == head ){
            return null;
        }
        queue.add(String.valueOf(head.value));
        while(!queue.isEmpty()){
            String poll = queue.poll();
        }
        return queue;
    }


    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }


    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
//            Queue<String> pre = preSerial(head);
//            Queue<String> pos = posSerial(head);
//            Queue<String> level = levelSerial(head);
//            Node preBuild = buildByPreQueue(pre);
//            Node posBuild = buildByPosQueue(pos);
//            Node levelBuild = buildByLevelQueue(level);
//            if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
//                System.out.println("Oops!");
//            }
        }
        System.out.println("test finish!");

    }
}
